Андрей и Олег очень любят работать, но у них нет своего офиса. Поэтому они работают в коворкингах.

Всего в доме $n$ коворкингов, расположенных на одной прямой. $i$ -й коворкинг имеет координату $a_i$ на этой прямой. Никакие два коворкинга не находятся в одной точке. У каждого коворкинга есть режим работы: $i$ -й коворкинг открывается в момент времени $o_i$ и закрывается в момент времени $c_i$ .

Андрей и Олег хотят провести максимально возможное время в коворкингах. За единицу времени они могут переместиться влево либо вправо, изменив свою координату на -1 или 1 соответственно. Помогите им найти максимальное время пребывания в коворкингах. В момент времени 0 они находятся в точке с координатой 0.

Формат ввода

В первой строке задано одно число $n \ (1 \leq n \leq 10^5)$ — количество коворкингов. В каждой из следующих $n$ строк находится по три целых числа $a_i, o_i, c_i \ (1 \leq a_i \leq 10^8, 1 \leq o_i < c_i \leq 10^8)$ — координата $i$ -го коворкинга, время открытия и закрытия $i$ -го коворкинга.

Формат вывода

Выведите одно число — максимальное время пребывания Андрея и Олега в коворкингах.

Система оценивания

В этой задаче проверка осуществляется по подгруппам. Баллы за первую и вторую подгруппы начисляются в случае прохождения всех тестов в них. Подгруппы 3 и 4 содержат 10 тестов, каждый из которых оценивается в 3 балла.

Обозначим максимальное значение $c_i$ по всем $i$ от 1 до $n$ как $C$ .

Обозначим максимальное значение $a_i$ по всем $i$ от 1 до $n$ как $A$ .

Подзадача	Баллы	Дополнительные ограничения	Необходимые подзадачи
1	30	$n \leqslant 1000, A, C \leqslant 10000$	-
2	40	$n \leqslant 1000$	1
3	18	$A, C \leqslant 2 \cdot 10^5$	1, 2
4	12	нет	1, 2, 3

Пример 1

Ввод	Вывод
2 1 1 6 2 5 8	6

Пример 2

Ввод	Вывод
4 4 5 8 1 11 16 6 11 15 8 17 19	9

Примечания

В первом примере оптимальной стратегией для Олега и Андрея будет следующая: с самого начала (момент 0, координата 0) им нужно выдвинуться в координату 1 (в первый коворкинг). Они придут туда в момент времени 1. С момента времени 1 до момента 6 они пробудут в первом коворкинге, после чего он закроется. В момент 6 Андрей и Олег начнут движение из координаты 1 в координату 2, во второй коворкинг. Они придут в коворкинг в момент времени 7, и он закроется в 8. Итоговый ответ: $(6 - 1) + (8 - 7) = 5 + 1 = 6$ .